/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-10-11
 * Time: 19:49
 */

/**
 *
 */
public class MissingNumber {
    public int takeAttendance(int[] records) {

        /**
         * 1.方法一用哈希表：记录存在的数字，找到哈希表为空的数字输出
         */
        // Set<Integer> set = new HashSet<>();
        // for(int x : records) set.add(x);

        // for(int i = 0; i < set.size(); i++){
        // if(!set.contains(i)) return i;
        // }
        // return set.size();

        /**
         * 方法二：位运算异或
         */

        // int ret = 0;
        // for (int i = 0; i < records.length; i++) {
        //     ret ^= records[i];
        //     ret ^= i + 1;
        // }

        // return ret;

        /**
         方法三：直接遍历
         */

        // int ret = 0;
        // for(int i = 0; i < records.length; i++){
        //     if(records[i] != i) return i;
        // }
        // return records.length;


        /**
         方法四：二分查找：
         */

        int left = 0,right = records.length-1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(records[mid] == mid) left = mid+1;
            else right = mid;
        }

        //特殊情况：整个数组元素及对应下标都一样时
        return records[left] == left ? left+1 : left;
    }
}
